//
//  BFSSolution.cpp
//  labuladong
//
//  Created by 刘振舟 on 2023/8/31.
//

#include "BFSSolution.hpp"



int BFSSolution::minDepth(TreeNode *root) { 
    if (!root) {
        return 0;
    };
    
    int minDepth = 1;
    queue<TreeNode *> treeQueue;
    treeQueue.push(root);
    TreeNode *node;
    while (!treeQueue.empty()) {
        int size = treeQueue.size();
        for (int i = 0; i < size; ++i) {
            node = treeQueue.front();
            treeQueue.pop();
            if (!node->left && !node->right) {
                return minDepth;
            } else if (node->left) {
                treeQueue.push(node->left);
            } else {
                treeQueue.push(node->right);
            }
        }
        ++minDepth;
    }
    
    return minDepth;
}

string plusOne(string str, int index) {
    if (str[index] == '9') {
        str[index] = '0';
    } else {
        str[index] += 1;
    }
    return str;
}

string minusOne(string str, int index) {
    if (str[index] == '0') {
        str[index] = '9';
    } else {
        str[index] -= 1;
    }
    return str;

}

int BFSSolution::openLock(vector<string> &deadends, string target) { 
    unordered_set<string> deads;
    for (string str : deadends) {
        deads.insert(str);
    }
    int step = 0;
    unordered_set<string> visited;
    queue<string> queue;
    
    visited.insert("0000");
    queue.push("0000");
    
    while (!queue.empty()) {
        int size = queue.size();
        
        for (int i = 0; i < size; ++i) {
            string cur = queue.front();
            queue.pop();
            
            if (deads.count(cur)) {
                continue;
            }
            if (target == cur) {
                return step;
            }
            for (int j = 0; j < 4; ++j) {
                string plus = plusOne(cur, j);
                if (!visited.count(plus)) {
                    queue.push(plus);
                    visited.insert(plus);
                }
                string minus = minusOne(cur, j);
                if (!visited.count(minus)) {
                    queue.push(minus);
                    visited.insert(minus);
                }
            }
        }
        ++step;
    }
    return -1;
}

